package cn.mayday.algorithms.year2021.month1.C滑动窗口其实即使双指针;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 30. 串联所有单词的子串
 * <p>
 * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 * <p>
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
 *
 * @author: mayday
 * @date: 2021/5/11 23:38
 * @version: 1.0
 */
public class Leetcode30FindSubstring {

    public static void main(String[] args) {
        String input1 = "barfoothefoobarman";
        String[] input2 = {"foo", "bar"};
        new Leetcode30FindSubstring().findSubstring(input1, input2);
//        System.out.println("result1 ===" + result1);
    }


//    思路
//    总共用到两个哈希表，allWords 用于记录words中单词出现的次数，subWords 用于记录子串中（也就是滑动窗口中）单词出现的次数
//    wordNum 为单词的个数，wordLen为单词长度
//    遍历字符串，移动长度为 wordNum * wordLen 的滑动窗口，再在当前滑动窗口中依次比较wordLen长度的单词
//    当这个窗口内一旦出现不存在allWords中的单词，或者这个单词在子串中出现的次数已经等于allWords中的次数(也就是再加入这个子串次数就要超出了)，这个滑动窗口就不符合要求，直接break进入下一个滑动窗口的匹配
//    一旦完全匹配上了，把滑动窗口的起始索引加入结果res中
//    还可以进一步优化，比如滑动窗口的每次移动可以移动一个单词长度而不是一个个字符移动，字符串匹配时第二个哈希表只移除第一个单词而不是完全置空等。可以参考这篇题解的解法二，太麻烦了，我放弃了。
//
//    作者：edelweisskoko
//    链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/30-chuan-lian-suo-you-dan-ci-de-zi-chuan-bvy9/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


    /**
     * 方法：滑动窗口 + 哈希表
     * 滑动串口算法总结：确定窗口左右边界，确定窗口移动大小
     *
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {

        // 记录所有单词出现的次数
        Map<String, Integer> allWords = new HashMap<>();
        for (String word : words) {
            allWords.put(word, allWords.getOrDefault(word, 0) + 1);
        }

        int wordNum = words.length; // 待比较单词的个数
        int wordLen = words[0].length(); // 首个单词的长度，其实因为每个单词长度相同
        List<Integer> result = new ArrayList<>(); // 索引的结果记录

        // 遍历字符串
        int right = s.length() - wordNum * wordLen + 1; // 滑动窗口的最右边
        for (int i = 0; i < right; i++) { // 遍历滑动窗口，i表示其实位置

            // key：字符 value：次数
            Map<String, Integer> subWords = new HashMap<>();
            int index = i;

            // 移动长度为 wordNum * wordLen 的滑动窗口，再在当前滑动窗口中依次比较wordLen长度的单词
            while (index < i + wordNum * wordLen) { // 滑动串口内，依次截取指定长度的单词
                String curWord = s.substring(index, index + wordLen);
                if (!allWords.containsKey(curWord)) {
                    break; // 判断，如果截取单词不在所有单词内；
                } else {
                    if (subWords.get(curWord) == allWords.get(curWord)) {
                        break; // 反之， 这个单词在子串中出现的次数已经等于allWords中的次数(也就是再加入这个子串次数就要超出了)
                    }
                }
                // 将子单词放入子Map中，并计数
                subWords.put(curWord, subWords.getOrDefault(curWord, 0) + 1);
                index += wordLen; // 索引更新
            }
            // 整理输出结果，
            if (index == i + wordNum * wordLen) {
                result.add(i);
            }
        }
        return result;
    }
//
//    作者：edelweisskoko
//    链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/30-chuan-lian-suo-you-dan-ci-de-zi-chuan-bvy9/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

}
